The present invention relates to data processing in the field of network management. The invention relates more specifically to methods and mechanisms for representing abstract network management policies and processing such policies, including conflict resolution.
Computer networks have become ubiquitous in the home, office, and industrial environment. As computer networks have grown ever more complex, automated mechanisms for organizing and managing the networks have emerged. These mechanisms are generally implemented in the form of one or more computer programs, and are generically known as network management systems or applications.
The behavior of some network management applications or equipment may be governed by one or more abstract policies. A network management policy expresses a business goal for use of the network; the network management application can convert the policy into instructions to network devices, such as switches, routers, and other hardware and software, to implement the policy. An example of a policy is: xe2x80x9cAll administrative assistants may use the World Wide Web only between 11 a.m. and 3 p.m., Monday through Friday.xe2x80x9d A system that can receive and act on such policies is sometimes called a policy-based network management system.
Policy-based management is used in other, specific contexts within the broad field of network management. For example, Cisco Centri Firewall software product, commercially available from Cisco Systems, Inc. of San Jose, Calif., is a policy-driven product. The use of policies to control a firewall is disclosed in co-pending U.S. patent application Ser. No. 60/074945, filed Feb. 17, 1998, entitled xe2x80x9cGraphical Network Security Policy Management,xe2x80x9d and naming Scott L. Wiegel as inventor. Problems involved in defining and resolving conflicts of network management policies are described in co-pending U.S. patent applications Ser. Nos. 09/205,833 and 09/205,831 filed Dec. 3, 1998, and respectively entitled xe2x80x9cAutomatically Verifying Network Management Policiesxe2x80x9d and xe2x80x9cRecognizing and Processing Conflicts in Network Management Policiesxe2x80x9d, each naming as inventors John Ahlstrom and Stephen I. Schleimer.
A proposed policy networking system to be developed by Cisco Systems, Inc. is known as xe2x80x9cCiscoAssurexe2x80x9d. Other information about policy-based networking is described in CiscoAssure Policy Networking: Enabling Business Applications through Intelligent Networking, http://www.cisco.com/warp/public/734/capn/assur sd.htm (posted Jun. 13, 1998); CiscoAssure Policy Networking End-to-End Quality of Service, http://www. cisco.com/ warp/public/734/capn/caqos wp.htm (posted Jun.24, 1998); Delivering End-to-End Security in Policy-Based Networks, http://www.cisco. com/warp/public/734/capn/deesp wp.htm (posted Sep. 11, 1998); User Registration and Address Management Services for Policy Networking, http://www.cisco.com/warp/public/734/capn/point wp.htm (posted Sep. 11, 1998); CiscoAssure User Registration Tool, http://www.cisco.com/warp/public/734/ capn/caurt ai.htm (posted Oct. 8, 1998).
Many problems in network management and policy administration can be expressed in terms of searching for a solution among a possible set of outcomes while simultaneously satisfying a set of requirements. For example, configuration of a network device must take into account parameters or variables such as software release version, types of interface, chassis, and also interoperability constraints with other networking devices. Only certain parameter values are compatible or will work together. Often compatible parameter values or configurations may be determined only by extensive study of documentation or specifications of the network devices, yet violation of these compatibility rules may cause a network failure. An example is linking together two switch ports, where a port on one side is full duplex and a port on the other side is half duplex. The network may not operate because the two ports or sides are incompatible.
These problems are especially acute in policy networking systems. A system administrator may establish two or more policies that conflict. Obscure or hidden incompatibilities may be overlooked when the policies are created. A conflict in network policies may cause network failure or undefined results.
A policy can also be represented as a set of variables that satisfy some criteria. For example, a policy might allow all packets from an electronic commerce application to have high priority whereas mass unsolicited c-mail messages must have very low priority. Thus, the variables of the policy are application type and priority level. The variables satisfy the criteria only by observing certain xe2x80x9cconstraints.xe2x80x9d In this example, the constraints are the association of e-commerce packets to high priority and e-mail packets to low priority.
The field of constraint logic programming (CLP) combines techniques from mathematics, artificial intelligence and operations research. In CLP, known elements of a problem are represented by a set of declarations, and permissible or viable solutions are found using algorithmic search methods. Generally, a Constraint Satisfaction Problem (CSP) consists of a set of variables V={V1, . . . , Vn}. For each variable Vi, there is a finite set Di of possible values (its Domain). The CSP further comprises a set of constraints that restrict the values that the variables can simultaneously take. A solution of a CSP is an assignment of values to each variable such that none of the constraints are violated. Constraints in FINITE and DISCRETE domains can be expressed as compatibility relations between variable-value tuples stating that certain combinations are allowed or not allowed.
Further information about CLP and CSPs are provided in: V. Kumar, Algorithms for Constraint Satisfaction Problems: A Survey, AI Magazine 13(1):32-44, 1992; M. Sabin et al., Constraint-Based Modeling: From Diagnosis and Configuration to Network Management, Department of Computer Science, University of New Hampshire, Durham, N.H. 03824; M. Wallace, Constraint Programming, IC-Parc, William Penny Laboratory, Imperial College, London, September 1995; R. Bartxc3xa1k, Guide to Constraint Programming, http://kti.ms.mff.cuni.cz/3bartak/constraints/, May 27, 1998. Further, E. Bruchez et al. of Artificial Intelligence Laboratory, Computer Science Department, Lausanne, Switzerland have implemented a general CSP solving system called Java Constraint Library, which is available for download online.
Based on the foregoing, there is a clear need in policy networking systems to prevent or resolve conflicts in network management policies.
There is also a need for a mechanism that can clearly express, store and enforce rules, specifications, or other statements of restrictions, requirements, or constraints on values of parameters that apply to network devices.
There is a particular need for such a mechanism in a network management system, whereby the mechanism prevents the creation or enforcement of erroneous or conflicting network management policies.
The foregoing needs and objects, and other needs and objects that will become apparent from the following description, are achieved by the invention, which comprises, in one aspect, a method of managing a network according to a plurality of network management policies, comprising the computer-implemented steps of storing each of the policies as a first constraint; storing at least one collective constraint in association with the first constraint; applying a constraint satisfaction algorithm to the first constraint to determine a solution or a set of solutions; checking whether addition of a solution or the set of solutions taken together violates any of the collective constraints; identifying a conflict in the policies when one or more of the instance or collective constraints is violated; and resolving the conflict by modifying one or more of the variables, values or restrictions.
One feature of this aspect is that storing each of the policies as a constraint comprises the steps of storing each of the policies as a constraint that comprises one or more variables, a set of possible values, and a set of restrictions on the values that the variables can simultaneously take. A related feature is that storing at least one collective constraint comprises the steps of storing one or more collective constraints in which at least one of the collective constraints is that none of the variables may interfere with one another. Another related feature is that applying a constraint satisfaction algorithm comprises the steps of applying a constraint satisfaction algorithm to the stored variables, values, restrictions, to the instance constraints to create zero or more solutions; and checking the collective constraints to test whether the new proposed solution does not conflict with any solutions already in the system.
According to another feature, resolving the conflict by modifying one or more of the variables, values or restrictions further comprises the step of adding a new constraint that defines the modified variable, value or restriction. Another feature is that storing each of the policies as a constraint comprises the steps of storing each of the policies as an instance constraint that comprises one or more variables, a set of possible values, and a set of restrictions on the values that the variables can simultaneously take. Still another feature is that storing one or more collective constraints comprises the steps of storing one or more group constraints, in which at least one of the group constraints is that none of the variables may interfere with one another.
The invention also encompasses a computer-readable medium that may be in the form of a carrier wave, and an apparatus that are configured to carry out the foregoing steps.